import java.awt.Point;
import java.awt.geom.Point2D.Float;
import java.awt.Graphics2D;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author base code by Chip Klostermeyer @
 *         http://www.unf.edu/~wkloster/3540/234tree.java modified by Team C
 *         2-3-4 Node implementation by Team C
 * 
 * @param <AnyType>
 *            type of element for the node
 */
public class Node234<AnyType extends Comparable<? super AnyType>> {

	/**
	 * All the possible states of any Node234 in a 234 Tree
	 * 
	 * @author Simeon Gbolo
	 * 
	 */
	public enum Node234State
	{
		moving, paused
	}

	// the current location on the node in the x,y plane
	private Float currentXYlocation;

	// the current destination of the node in the x,y plane
	private Float currentXYdestination;

	private Float startingPoint;

	// running time for this animation
	float runningTime;

	// used to calculate the slope for moving from one point to another
	float rise;

	// Used to calculate the slope for moving from one spot to another
	float run;

	// a path for this node to follow
	Queue<Float> path;

	Node234State state;

	// Minimum node rectangle height)
	private static final int MIN_DRAW_HT = 20;
	// Minimum horizontal gap between nodes
	private static final int MIN_HGAP = 10;
	// Minimum vertical gap between nodes
	private static final int MIN_VGAP = 60;
	// B-tree order value
	public static final int ORDER = 4;

	private int drawHeight;
	private int numElements;
	private Node234<AnyType> parent;
	private Node234<AnyType>[] childArray;
	private DataElement234<AnyType>[] elementArray;
	private Point center;

	public Node234()
	{
		childArray = new Node234[ORDER];
		elementArray = new DataElement234[ORDER - 1];
		parent = null;
		numElements = 0;
		center = null;
		drawHeight = MIN_DRAW_HT;
		currentXYlocation = new Float();// added simeon
		currentXYdestination = new Float();// added simeon
		startingPoint = new Float();// added simeon
		path = new LinkedList<Float>();// added simeon
		runningTime = 0;// added simeon
		state = Node234State.paused;// added simeon
	}

	/**
	 * Returns an array containing all children of this parent node
	 * 
	 * @return the array of child nodes
	 */
	public Node234<AnyType>[] getChildArray()
	{
		return childArray;
	}

	/**
	 * Returns an array of all DataElement234 objects in this node
	 * 
	 * @return the array of elements
	 */
	public DataElement234<AnyType>[] getElementArray()
	{
		return elementArray;
	}

	/**
	 * Connects a child to this node
	 * 
	 * @param childNum
	 *            - child array index where the node will be connected to
	 * @param child
	 *            - the child to be connected
	 */
	public void connectChild(int childNum, Node234<AnyType> child)
	{
		childArray[childNum] = child;
		if (child != null)
			child.parent = this;
	}

	/**
	 * Disconnects a child from this node
	 * 
	 * @param childNum
	 *            - the index of the child in this node's child array
	 * 
	 * @return the child that was disconnected
	 */
	public Node234<AnyType> disconnectChild(int childNum)
	{
		Node234<AnyType> tempNode = childArray[childNum];
		childArray[childNum] = null;
		return tempNode;
	}

	/**
	 * Obtains the child node at the given child array index
	 * 
	 * @param index
	 *            - the index within this node's child array
	 * @return the child node at the given index
	 */
	public Node234<AnyType> getChild(int childNum)
	{
		return childArray[childNum];
	}

	/**
	 * Returns the index of the given key, within this node's element array (-1
	 * if key is not found)
	 * 
	 * @param key
	 *            - the search key
	 * @return the location (element index) of the search key
	 */
	public int getElementIndex(AnyType key)
	{
		// int index = -1;

		for (int i = 0; i < numElements; i++)
		{
			if (elementArray[i].getKey() == key)
			{
				return i;
			}
		}

		// return index;
		return -1;
	}

	/**
	 * Used to reset the parent of children of this node. This is used when a
	 * child is moved from one node to another during delete.
	 */
	private void resetParents()
	{
		for (int i = 0; i < 4; i++)
		{
			if (childArray[i] != null)
			{
				childArray[i].parent = this;
			}
		}
	}

	/**
	 * @author Eric Berry Deletes the specified key from the tree rooted at this
	 *         node. Recursive calls are made to subsequent child nodes, until
	 *         the key is found and can be handled, or it is determined that the
	 *         key cannot be found.
	 * 
	 * @param key
	 *            - the value to be removed from the tree
	 */
	public void delete(AnyType key)
	{

		if (findElement(key))
		{
			if (isLeaf())
			{
				// case 1: Node is a Leaf
				removeElement(key);
			} else
				if (!isLeaf())
				{
					// case 2: internal node
					// get the index of the eleemnt
					int kIndex = getElementIndex(key);

					// get the predecessor and successor child nodes of the
					// element
					Node234<AnyType> preChildNode = getChild(kIndex);
					Node234<AnyType> sucChildNode = getChild(kIndex + 1);

					if (preChildNode != null
							&& preChildNode.getNumElements() >= 2)
					{
						// 2a

						// get the previous element of this element in the
						// predecessor sub tree, set this element to the
						// position
						// of the element being deleted
						Node234<AnyType> kPrimeNode = preChildNode
								.getMaximumNode();
						DataElement234<AnyType> kPrimeElement = kPrimeNode
								.getElement(kPrimeNode.getNumElements() - 1);
						setElement(kIndex, kPrimeElement);

						// recursively delete the predecessor element from the
						// predecessor sub tree
						preChildNode.delete(kPrimeElement.getKey());
					} else
						if (preChildNode != null
								&& preChildNode.getNumElements() == 1)
						{
							if (sucChildNode != null
									&& sucChildNode.getNumElements() >= 2)
							{
								// 2b

								// get the next element of this element in the
								// successor sub tree, set this element to the
								// position of the element being deleted
								Node234<AnyType> kPrimeNode = sucChildNode
										.getMinimumNode();
								DataElement234<AnyType> kPrimeElement = kPrimeNode
										.getElement(0);
								setElement(kIndex, kPrimeElement);
								sucChildNode.delete(kPrimeElement.getKey());
							} else
								if (sucChildNode != null)
								{
									// 2c
									// merge predecessor and successor

									// insert the element being deleted and the
									// one element
									// in the successors node into the
									// predecessor node
									preChildNode
											.insertElement(elementArray[kIndex]);
									preChildNode.insertElement(sucChildNode
											.getElement(0));

									// remove the deleted element from it's
									// original node
									removeElementAtIndex(kIndex);

									// reset the proper children of the
									// successor and
									// predecessor nodes
									preChildNode.childArray[2] = sucChildNode.childArray[0];
									preChildNode.childArray[3] = sucChildNode.childArray[1];
									sucChildNode.childArray[0] = null;
									sucChildNode.childArray[1] = null;

									// reset the parents of the moved children
									preChildNode.resetParents();

									// reset the childArray of the node
									// originally holding
									// the deleted element
									for (int i = kIndex + 1; i < childArray.length; i++)
									{
										if (i + 1 < childArray.length)
										{
											childArray[i] = childArray[i + 1];
										} else
										{
											childArray[i] = null;
										}
									}

									// recursively delete the key from the new
									// merged node
									preChildNode.delete(key);
								}
						}
				}
		}
		// When a leaf node is reached and element is not found,
		// it is not in tree
		// else if (findElement(key) != true) {
		else
			if (!isLeaf())
			{
				// case 3

				// get the sub root of the tree that should have the element in
				// it
				int srIndex = getSubrootIndex(key);
				Node234<AnyType> subRoot = childArray[srIndex];

				if (subRoot.getNumElements() == 1)
				{
					// if subroot has only one item
					Node234<AnyType> preSibling = null;
					Node234<AnyType> sucSibling = null;

					// setup predecessor and successor sibling indexes as
					// necessary
					if (srIndex > 0)
					{
						preSibling = childArray[srIndex - 1];
					}

					if (srIndex < 3)
					{
						sucSibling = childArray[srIndex + 1];
					}

					if (preSibling != null && preSibling.getNumElements() > 1)
					{
						// Case 3a pre
						// get predecessor element and the element to be moved
						// down
						// into the node
						DataElement234<AnyType> preElement = preSibling
								.getElement(preSibling.numElements - 1);
						DataElement234<AnyType> downElement = getElement(srIndex - 1);

						// remove the element being moved down and insert the
						// predecessor and the downward element into the proper
						// node
						removeElementAtIndex(srIndex - 1);
						subRoot.insertElement(downElement);
						insertElement(preElement);

						// reset the childArray
						subRoot.childArray[3] = subRoot.childArray[2];
						subRoot.childArray[2] = subRoot.childArray[1];
						subRoot.childArray[1] = subRoot.childArray[0];
						subRoot.childArray[0] = preSibling.childArray[preSibling.numElements];

						// reset the parent of the moved children
						subRoot.resetParents();

						// remove the child from from the preSibling
						preSibling.childArray[preSibling.numElements] = null;

						// remove the last element from the preSibling
						preSibling.removeItem();

						// recursively delete the key from the subroot
						subRoot.delete(key);

					} else
						if (sucSibling != null
								&& sucSibling.getNumElements() > 1)
						{
							// Case 3a suc

							// get successor element and the element to be moved
							// down
							// into the node
							DataElement234<AnyType> sucElement = sucSibling
									.getElement(0);
							DataElement234<AnyType> downElement = getElement(srIndex);

							// remove the element being moved down and insert
							// the
							// predecessor and the downward element into the
							// proper node
							removeElementAtIndex(srIndex);
							subRoot.insertElement(downElement);
							insertElement(sucElement);

							// add the child from successor sibling to the sub
							// root
							subRoot.childArray[2] = sucSibling.childArray[0];

							// reset the parents of the moved children
							subRoot.resetParents();

							// reset the successor siblings array
							sucSibling.childArray[0] = sucSibling.childArray[1];
							sucSibling.childArray[1] = sucSibling.childArray[2];
							sucSibling.childArray[2] = sucSibling.childArray[3];
							sucSibling.childArray[3] = null;

							// delete the moved element from the successor
							sucSibling.removeElementAtIndex(0);

							// recursively delete the key from the sub root
							subRoot.delete(key);
						} else
						{
							if (preSibling != null)
							{
								// Case 3b pre
								// get the element from the sub root and the
								// element to
								// be moved down
								DataElement234<AnyType> subRootElement = subRoot
										.getElement(0);
								DataElement234<AnyType> downElement = getElement(srIndex - 1);

								// remove the obtained elements from their nodes
								subRoot.removeElementAtIndex(0);
								removeElementAtIndex(srIndex - 1);

								// move the children from the sub root to the
								// siblings node
								preSibling.childArray[2] = subRoot.childArray[0];
								preSibling.childArray[3] = subRoot.childArray[1];

								// reset the parent of the moved children
								preSibling.resetParents();

								// insert the elements into the siblings node
								preSibling.insertElement(downElement);
								preSibling.insertElement(subRootElement);

								// reset this nodes children to remove the
								// reference
								// to the subroot
								for (int i = srIndex; i < childArray.length; i++)
								{
									if (i + 1 < childArray.length)
									{
										childArray[i] = childArray[i + 1];
									} else
									{
										childArray[i] = null;
									}
								}

								// recursively delete the key from the merged
								// nodes
								// sub tree
								preSibling.delete(key);
							} else
							{
								// 3b suc
								// get the element from the sub root and the
								// element to
								// be moved down
								DataElement234<AnyType> subRootElement = subRoot
										.getElement(0);
								DataElement234<AnyType> downElement = getElement(srIndex);

								// remove the obtained elements from their nodes
								subRoot.removeElementAtIndex(0);
								removeElementAtIndex(srIndex);

								// insert the elements into the siblings node
								sucSibling.insertElement(subRootElement);
								sucSibling.insertElement(downElement);

								// move the children from the sub root to the
								// siblings node
								sucSibling.childArray[3] = sucSibling.childArray[1];
								sucSibling.childArray[2] = sucSibling.childArray[0];
								sucSibling.childArray[1] = subRoot.childArray[1];
								sucSibling.childArray[0] = subRoot.childArray[0];

								// reset the parent of the moved children
								sucSibling.resetParents();

								// reset this nodes children to remove the
								// reference
								// to the sub root
								for (int i = srIndex; i < childArray.length; i++)
								{
									if (i + 1 < childArray.length)
									{
										childArray[i] = childArray[i + 1];
									} else
									{
										childArray[i] = null;
									}
								}
								// recursively delete the key from the merged
								// node's
								// sub tree
								sucSibling.delete(key);
							}
						}
				} else
					if (subRoot.numElements > 1)
					{
						// if the sub root already has 2 or 3 elements just
						// recursively
						// delete on the sub root
						subRoot.delete(key);
					}
			}
	}

	/**
	 * Returns the parent of this child node
	 * 
	 * @return this node's parent node
	 */
	public Node234<AnyType> getParent()
	{
		return parent;
	}

	/**
	 * Returns whether this node has any child nodes (i.e. - a leaf node has no
	 * children)
	 * 
	 * @return whether this is a leaf node or not
	 */
	public boolean isLeaf()
	{
		return (childArray[0] == null) ? true : false;
	}

	/**
	 * Returns the number of elements within this node
	 * 
	 * @return the element count
	 */
	public int getNumElements()
	{
		return numElements;
	}

	/**
	 * Returns the element at the given index
	 * 
	 * @param index
	 *            - the index of the desired element
	 * @return the element located at the specified index
	 */
	public DataElement234<AnyType> getElement(int index)
	{
		return elementArray[index];
	}

	/**
	 * Assigns the given element, at the given array index
	 * 
	 * @param index
	 *            - the index within this node's element array
	 * @param e
	 *            - the element to be assigned at the array location
	 */
	public void setElement(int index, DataElement234<AnyType> e)
	{
		elementArray[index] = e;
	}

	/**
	 * Returns the index of the child node
	 * 
	 * @param child
	 *            - the child to get the index of
	 * @return the index of the child in the child array
	 */
	public int getChildIndex(Node234<AnyType> child)
	{
		int index = 0;

		while (childArray[index] != child)
		{
			index++;
		}

		return index;
	}

	/**
	 * Returns whether this node has the maximum number of elements
	 * 
	 * @return boolean value stating whether the node has the maximum number of
	 *         elements
	 */
	public boolean isFull()
	{
		return (numElements == ORDER - 1) ? true : false;
	}

	/**
	 * Calculates the total depth of all elements in this node's sub-tree,
	 * assuming that this node's depth is equal to a given depth.
	 * 
	 * @param start_depth
	 *            - assumed depth of this node's elements
	 * @return the total of all child node elements' depths
	 */
	public int getTotalDepths(int start_depth)
	{

		// Sum of child node depths
		int depths = 0;

		// Node without children returns its elements depths
		if (this.isLeaf())
		{
			return start_depth * numElements;
		}

		// Compare remaining child heights (Child count = Elements + 1)
		for (int i = 0; i <= numElements; i++)
		{
			if (childArray[i] != null)
			{
				// Total average children depths, based on parent depth + 1
				depths += childArray[i].getTotalDepths(start_depth + 1);
			}
		}

		// Add depths of all elements at this node to total
		return depths + (start_depth * numElements);
	}

	/**
	 * Calculates the maximum height of this node, based on the height of its
	 * child nodes
	 * 
	 * @return the greatest height value of any child, increased by one
	 */
	public int getHeight()
	{
		int height;

		if (this.isLeaf())
		{
			return 0;
		}

		// Initial height of minimum child node
		height = childArray[0].getHeight();

		// Compare remaining child heights (Child count = Elements + 1)
		for (int i = 1; i <= numElements; i++)
		{
			if (childArray[i] != null)
			{
				height = Math.max(height, childArray[i].getHeight());
			}
		}

		// Maximum height of any child node + 1
		return height + 1;
	}

	/**
	 * Calculates the size of the sub-tree at this node
	 * 
	 * @return the total number of data elements in the sub-tree
	 */
	public int getElementSize()
	{
		// Initialize with size of this node
		int sum_sizes = numElements;

		if (!this.isLeaf())
		{
			// Add sizes of child nodes (Child count = Elements + 1)
			for (int i = 0; i <= numElements; i++)
			{
				if (childArray[i] != null)
				{
					sum_sizes += childArray[i].getElementSize();
				}
			}
		}

		return sum_sizes;
	}

	/**
	 * Calculates the size of the sub-tree at this node
	 * 
	 * @return the total number of nodes in the sub-tree
	 */
	public int getSize()
	{
		// Count this node in sum of nodes
		int sum_nodes = 1;

		if (!this.isLeaf())
		{
			// Add number of child nodes (Child count = Elements + 1)
			for (int i = 0; i <= numElements; i++)
			{
				if (childArray[i] != null)
				{
					sum_nodes += childArray[i].getSize();
				}
			}
		}

		return sum_nodes;
	}

	/**
	 * Returns whether the key is in the node
	 * 
	 * @param key
	 *            key of DataElement to be found
	 * @return boolean of whether the key is in the node
	 */
	public boolean findElement(AnyType key)
	{
		for (int j = 0; j < ORDER - 1; j++)
		{
			if (elementArray[j] == null)
				break;
			else
				if (elementArray[j].getKey() == key)
				{
					elementArray[j].setFound(true);
					return true;
				}
		}

		return false;
	}

	/**
	 * Finds the index of the DataElement with the specified key in the
	 * elementArray
	 * 
	 * @param key
	 *            key of the DataElement whose index is to be found
	 * @return index of the DataElement containing the key in the elementArray
	 * @throws ItemNotFoundException
	 */
	public int findElementIndex(AnyType key) throws ItemNotFoundException
	{
		for (int j = 0; j < ORDER - 1; j++)
		{
			if (elementArray[j] == null)
				break;
			else
				if (elementArray[j].getKey() == key)
					return j;
		}

		throw new ItemNotFoundException();
	}

	/**
	 * Inserts the DataElement into the DataElement array for the node
	 * 
	 * @param newElement
	 *            element to be inserted
	 * @return the index in the elementArray of the newly added item
	 */
	public int insertElement(DataElement234<AnyType> newElement)
	{
		// assumes node is not full
		numElements++;

		// key of new item
		AnyType newKey = newElement.getKey();

		// start on right, examine items, if item null, go left one cell
		// not null get it's key
		for (int j = ORDER - 2; j >= 0; j--)
		{
			if (elementArray[j] == null)
				continue;
			else
			{
				AnyType itsKey = elementArray[j].getKey();
				if (newKey.compareTo(itsKey) < 0)
					// if it's bigger shift it right
					elementArray[j + 1] = elementArray[j];
				else
				{
					elementArray[j + 1] = newElement;
					return j + 1;
				}
			}
		}
		elementArray[0] = newElement;
		return 0;
	}

	/**
	 * Removes the last DataElement from the Node
	 * 
	 * @return the DataElement that was removed
	 */
	public DataElement234<AnyType> removeItem()
	{
		DataElement234<AnyType> temp = elementArray[numElements - 1];
		elementArray[numElements - 1] = null;
		numElements--;
		return temp;
	}

	/**
	 * Removes the element with the specified key from the node
	 * 
	 * @param key
	 *            the key in a DataElement to be removed
	 */
	public void removeElement(AnyType key)
	{
		int i;
		for (i = 0; i < numElements; i++)
		{
			if (elementArray[i].getKey() == key)
			{
				elementArray[i] = null;
				break;
			}
		}

		for (; i < numElements - 1; i++)
		{
			elementArray[i] = elementArray[i + 1];
			elementArray[i + 1] = null;
		}

		numElements--;
	}

	/**
	 * Returns the maximum element in this node
	 * 
	 * @return the element with the largest key in this node
	 */
	public DataElement234<AnyType> getMaximumElement()
	{
		return elementArray[numElements - 1];
	}

	/**
	 * Removes a element at the specified index of the elementArray
	 * 
	 * @param index
	 *            index of the element to be removed
	 * @return the element that is removed
	 */
	public DataElement234<AnyType> removeElementAtIndex(int index)
	{
		DataElement234<AnyType> temp = elementArray[index];

		for (int i = index; i < numElements - 1; i++)
		{
			elementArray[i] = elementArray[i + 1];
			if (i + 1 > numElements - 1)
			{
				elementArray[i + 1] = null;
			}
		}
		numElements--;

		// this index cannot be larger than 2
		elementArray[numElements] = null;

		return temp;
	}

	/**
	 * @author Eric Berry Searches for the index of the root of a sub tree of
	 *         this node that should contain the key that we are searching for.
	 * @param key
	 *            the value whose subtree we are looking for
	 * @return the index of the child that is the root of the sub tree
	 *         containing the key
	 */
	public int getSubrootIndex(AnyType key)
	{
		int childIndex = 0;

		// increment the index until the element is smaller than the current
		// element in the element array
		while (childIndex < numElements - 1)
		{

			if (key.compareTo(elementArray[childIndex].getKey()) < 0)
			{
				return childIndex;
			}
			childIndex++;

		}

		// if the search element is larger than the last element in the node
		// increase the child index by 1
		if (key.compareTo(elementArray[childIndex].getKey()) > 0)
		{
			childIndex++;
		}

		return childIndex;
	}

	public void displayNodeConsole()
	{
		// for(int j=0; j<numItems; j++) {
		// elementArray[j].displayItem();
		// }
		// System.out.println("/");
		System.out.println(this);
	}

	/**
	 * 
	 * @param deltaTime
	 */
	public void updateMembers(float deltaTime)
	{
		for (int j = 0; j < numElements; j++)
			elementArray[j].advance(deltaTime);
	}

	/**
	 * Draws a graphic representation of the node, and its elements
	 * 
	 * @param graph_2d
	 *            - the graphics object for drawing
	 */
	public void drawNode(Graphics2D graph_2d)
	{
		// Rounded rectangle corner height & width
		int rect_radius;

		if (center != null)
		{
			rect_radius = drawHeight / 4;

			// Node border
			graph_2d.drawRoundRect(upperLeftX(), upperLeftY(), getDrawWidth(),
					drawHeight, rect_radius, rect_radius);

			for (int i = 0; i < elementArray.length; i++)
			{
				if (elementArray[i] != null)
				{
					elementArray[i].drawElement(graph_2d);
				} else
				{
					// Draw place-holder border
					drawEmptyElement(graph_2d, getElementCenter(i));
				}
			}

			for (int i = 0; i <= numElements; i++)
			{
				if (childArray[i] != null && childArray[i].getCenter() != null)
				{

					// Draws links from the parent to children nodes.
					graph_2d.drawLine(upperLeftX() + i * getDrawWidth()
							/ (ORDER - 1), upperLeftY() + drawHeight,
							(int) childArray[i].getCenter().getX(),
							childArray[i].upperLeftY());

					// call to draw child node recursively
					childArray[i].drawNode(graph_2d);
				}
			}

		}
	}

	/**
	 * Used to set up a nodes destination and it's data element's destinations -
	 * I pretty much copied the provided method above and did some refactoring!
	 */
	public void calculateDestination()
	{

		if (center != null)
		{
			Float xYDest = new Float();
			//
			xYDest.setLocation(upperLeftX(), upperLeftY());
			setUpForNavigation(xYDest);

			for (int i = 0; i < numElements; i++)
			{
				if (elementArray[i] != null)
				{
					elementArray[i].calculateElementDestination();
				} else
				{

				}
			}

			for (int i = 0; i < childArray.length; i++)
			{
				if (childArray[i] != null && childArray[i].getCenter() != null)
				{
					childArray[i].calculateDestination();
				}
			}

		}
	}

	/**
	 * Finds the left node at the greatest depth in this node's sub-tree (i.e. -
	 * the node containing the smallest elements in the sub-tree)
	 * 
	 * @return the left-most node in the sub-tree
	 */
	public Node234<AnyType> getMinimumNode()
	{
		if (this.isLeaf())
		{
			return this;
		}

		// Left-most node should contain minimum (smallest) elements
		return this.getChild(0).getMinimumNode();
	}

	/**
	 * Finds the right node at the greatest depth in this node's sub-tree (i.e.
	 * - the node containing the largest elements in the sub-tree)
	 * 
	 * @return the right-most node in the sub-tree
	 */
	public Node234<AnyType> getMaximumNode()
	{
		if (this.isLeaf())
		{
			return this;
		}

		// Right-most node should contain maximum (largest) elements
		return this.getChild(numElements).getMaximumNode();
	}

	/**
	 * Shifts the center coordinates of this node, and all the nodes in its
	 * sub-tree by a given amount
	 * 
	 * @param dx
	 *            - the delta X for the shift
	 * @param dy
	 *            - the delta Y for the shift
	 */
	public void moveCenter(int dx, int dy)
	{
		if (center != null)
		{
			center.translate(dx, dy);

			moveElementCenters(dx, dy);
			moveChildCenters(dx, dy);
		}
	}

	public void centerSubTree()
	{
		Node234<AnyType> min_node = null;
		Node234<AnyType> max_node = null;
		// Absolute center X for max extent of tree
		int base_center = 0;

		if (!this.isLeaf() && this.center != null)
		{

			min_node = this.getMinimumNode();
			max_node = this.getMaximumNode();

			if (min_node != null && min_node.center != null && max_node != null
					&& max_node.center != null)
			{
				// Half the total spanning width
				base_center = (max_node.center.x - min_node.center.x) / 2;
				// Subtracted from the absolute X position of max_node
				base_center = max_node.center.x - base_center;

				if (base_center - this.center.x != 0)
				{
					this.moveElementCenters(base_center - this.center.x, 0);
					this.center.translate(base_center - this.center.x, 0);

					for (int i = 0; i <= numElements; i++)
					{
						if (childArray[i] != null)
						{
							childArray[i].centerSubTree();
						}
					}
				}
			}
		}
	}

	public void compressSubTree()
	{
		Node234<AnyType> left = null;
		Node234<AnyType> right = null;
		// Gap between right edge of left node and left edge of right node
		int leaf_gap;

		if (!this.isLeaf())
		{
			for (int i = 1; i <= this.numElements; i++)
			{
				// Trap problematic tree causing NullPointer error
				if (this.childArray[i - 1] != null)
				{
					// Check left sub-tree
					this.childArray[i - 1].compressSubTree();
				} else
				{
					System.out.print(this + ": Compress (Left null)");
				}

				// Trap problematic tree causing NullPointer error
				if (this.childArray[i - 1] != null
						&& this.childArray[i] != null)
				{
					// Compare this left and right
					left = this.childArray[i - 1].getMaximumNode();
					right = this.childArray[i].getMinimumNode();

					if (left != null && left.center != null && right != null
							&& right.center != null)
					{

						leaf_gap = right.upperLeftX() - left.upperLeftX()
								- left.getDrawWidth();
						// System.out.println("Compression comparison");
						// Collapse (or expand) to gap width to minimum
						if (leaf_gap != MIN_HGAP)
						{
							// Shift right sub-tree
							childArray[i].moveCenter(MIN_HGAP - leaf_gap, 0);
							// System.out.println("Compression performed");
						}
					}
				} else
				{
					System.out.print(this + ": Compress (Left-Right nulls)");
				}

				// Trap NullPointer error
				if (this.childArray[i] != null)
				{
					// Check right sub-tree
					this.childArray[i].compressSubTree();
				} else
				{
					System.out.print(this + ": Compress (Right null)");
				}
			}
		}
	}

	/**
	 * Outputs the tree element order generated by an in-order traversal
	 * 
	 * @return the ordered tree elements
	 */
	public String inOrderTraversal()
	{
		StringBuilder element_order = new StringBuilder();

		for (int i = 0; i <= numElements; i++)
		{
			// Traverse through child nodes, when present
			if (!this.isLeaf())
			{
				element_order.append(childArray[i].inOrderTraversal());
			}

			// Element array has one less item
			if (i < numElements)
			{
				element_order.append("{" + elementArray[i] + "}");
			}
		}

		return element_order.toString();
	}

	/**
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString()
	{
		// return super.toString();
		StringBuilder node_string = new StringBuilder("Node(");

		// Output child links with respective data elements in between
		for (int i = 0; i < ORDER; i++)
		{
			if (this.childArray[i] == null)
			{
				node_string.append("{no-link}");
			} else
			{
				node_string.append("{linked}");
			}

			// Element array has one less item
			if (i < ORDER - 1)
			{
				if (this.elementArray[i] == null)
				{
					node_string.append("{null}");
				} else
				{
					node_string.append("{" + elementArray[i] + "}");
				}
			}
		}

		node_string.append(")");

		return node_string.toString();
	}

	private void moveChildCenters(int dx, int dy)
	{
		// Loop through child nodes
		if (!this.isLeaf())
		{
			// (Child count = Elements + 1)
			for (int i = 0; i <= numElements; i++)
			{
				if (childArray[i] != null)
				{
					// Propagate center shift to all children
					childArray[i].moveCenter(dx, dy);
				}
			}
		}
	}

	private void moveElementCenters(int dx, int dy)
	{
		// Loop through data elements
		for (int i = 0; i < numElements; i++)
		{
			if (elementArray[i] != null)
			{
				elementArray[i].moveCenter(dx, dy);
			}
		}
	}

	/**
	 * @return the center
	 */
	public Point getCenter()
	{
		return center;
	}

	/**
	 * @param center
	 *            the center to set
	 */
	public void setCenter(Point loc)
	{
		this.center = loc;

		// Set centers of data elements
		if (center != null)
		{

			for (int i = 0; i < numElements; i++)
			{
				if (elementArray[i] != null)
				{
					elementArray[i].setCenter(new Point(getElementCenter(i)));
				}
			}

			if (!this.isLeaf())
			{
				// Find height of children nodes
				int child_spacing = this.getHeight() - 1;
				// Maximum spacing factor
				int max_children = this.getMaxChildren();
				// Beginning child horizontal center position
				int center_x = this.center.x;
				// Common child vertical center position
				int center_y = this.center.y + this.getDrawHeight() + MIN_VGAP;

				// Calculate total spacing based on complete tree (max factor)
				child_spacing = (int) (Math.pow(max_children, child_spacing) * (MIN_HGAP + getDrawWidth()));

				// Start at left-most child, centering all spacing about parent
				center_x -= (child_spacing * (max_children - 1) / 2);

				// Loop to propagate change of center to all child nodes
				// (Child count = Elements + 1)
				for (int j = 0; j <= numElements; j++)
				{
					if (childArray[j] != null)
					{

						// Calculated center in relation to this.center
						childArray[j].setCenter(new Point(center_x, center_y));

						// Move to next horizontal center position
						center_x += child_spacing;
					}
				}
			}
		}
	}

	/**
	 * @return the total height of the drawn the node graphic
	 */
	public int getDrawHeight()
	{
		return drawHeight;
	}

	/**
	 * @param height
	 *            - the new total height for the drawn node graphic
	 */
	public void setDrawHeight(int height)
	{
		this.drawHeight = height < MIN_DRAW_HT ? MIN_DRAW_HT : height;
	}

	/**
	 * @return the total width of the drawn node graphic
	 */
	public int getDrawWidth()
	{
		return drawHeight * elementArray.length;
	}

	/**
	 * Calculates the upper-left X-coordinate for node graphic border
	 * 
	 * @return The center X-coordinate less half of border width
	 */
	public int upperLeftX()
	{
		return (int) (center.getX() - (this.getDrawWidth() / 2));
	}

	/**
	 * Calculates the upper-left Y-coordinate for node graphic border
	 * 
	 * @return The center Y-coordinate less half of border height
	 */
	public int upperLeftY()
	{
		return (int) (center.getY() - (drawHeight / 2));
	}

	/**
	 * 
	 * @return the maximum number of children of any node in this sub-tree
	 */
	private int getMaxChildren()
	{

		int child_max = this.getNumChildren();

		if (!this.isLeaf())
		{
			// (Child count = Elements + 1)
			for (int i = 0; i <= numElements; i++)
			{
				if (childArray[i] != null)
				{
					child_max = Math.max(child_max,
							childArray[i].getMaxChildren());
				}
			}
		}

		return child_max;
	}

	/**
	 * 
	 * @return the number of child nodes for this node
	 */
	private int getNumChildren()
	{
		if (this.isLeaf())
		{
			return 0;
		} else
		{

			// 2-3-4 tree property (child node count = element count + 1)
			return numElements + 1;
		}
	}

	/**
	 * Returns an appropriate center location, with respect to this node's
	 * location, where the element stored at the given array index should be
	 * drawn
	 * 
	 * @param element_index
	 *            - the array index where the node element is located
	 * @return the point of where this drawn element should be centered
	 */
	private Point getElementCenter(int element_index)
	{
		// Left edge of node rectangle
		// + radius of element circle
		// + center-to-center distance (element circle diameter leaves no gap)
		double center_x = (upperLeftX() + (0.5 + element_index) * drawHeight);

		return new Point((int) center_x, (int) center.getY());
	}

	/**
	 * Draws a place-holder representation of an empty element at the given
	 * location
	 * 
	 * @param graph_2d
	 *            - the graphic object for drawing
	 * @param loc
	 *            - the center location at which drawing is performed
	 */
	private void drawEmptyElement(Graphics2D graph_2d, Point loc)
	{
		DataElement234<AnyType> data = new DataElement234<AnyType>(null);
		data.setCenter(loc);
		data.drawElement(graph_2d);
	}

	/**
	 * This method makes the node update it's self depending on it's current
	 * state
	 * 
	 * @param deltaTime
	 */
	public void advance(float deltaTime)
	{

		if (state == Node234State.moving)
		{
			updateMoving(deltaTime);
		}

		if (state == Node234State.paused)
		{
			updatePaused(deltaTime);
		}

	}

	/**
	 * @author Simeon Gbolo depending on what ever is first point in the path
	 *         queue, the node will travel to that location. once it reaches
	 *         that location and if the Queue is not empty - it will move on to
	 *         the next point in the queue
	 * 
	 * @param deltaTime
	 *            the change in time
	 */
	private void updateMoving(float deltaTime)
	{
		runningTime += deltaTime;

		float newX = (float) (startingPoint.getX() + run * runningTime);
		float newY = (float) (startingPoint.getY() + rise * runningTime);
		currentXYlocation.setLocation(newX, newY);
		// System.out.println("" +getDistanceFromDestination() );
		if (getDistanceFromDestination() <= 2)
		{
			/*
			 * if (!path.isEmpty()) { setUpForNavigation(path.poll()); } else {
			 * 
			 * 
			 * 
			 * }
			 */
			currentXYlocation.setLocation(currentXYdestination);
			state = Node234State.paused;
		}
	}

	/**
	 * @author Simeon gbolo set running time to 0 and if the node is found while
	 *         paused add .5 to node counder until it reaches 1000 - then the
	 *         node will be back it's original color
	 * 
	 * @param deltaTime
	 */
	private void updatePaused(float deltaTime)
	{
		runningTime = 0;

	}

	/**
	 * @author Simeon Gbolo This method is used to calculate the distance from
	 *         one point to another. 04-14-2012
	 * @return The distance from one point to another
	 */
	public int getDistanceFromDestination()
	{

		return (int) currentXYlocation.distance(currentXYdestination);
	}

	/**
	 * @author Simeon Gbolo 04-14-2012
	 * @return the x current x location of this node
	 */
	public int getCurrentX()
	{

		return (int) currentXYlocation.getX();
	}

	/**
	 * @return the currentXYlocation
	 */
	public Float getCurrentXYlocation()
	{
		return currentXYlocation;
	}

	/**
	 * @author Simeon Gbolo 04-14-2012
	 * @return the current y location of this node
	 */
	public int getCurrentY()
	{

		return (int) currentXYlocation.getY();

	}

	/**
	 * @author Simeon gbolo Used to calculate the slope from one point to
	 *         another This should be called only once before navigating from
	 *         one point to another, This method also sets the new starting
	 *         point for your node's navigation
	 */
	public void getSlope()
	{
		rise = (float) (currentXYdestination.getY() - currentXYlocation.getY());
		run = (float) (currentXYdestination.getX() - currentXYlocation.getX());
		startingPoint.setLocation(currentXYlocation);
	}

	/**
	 * @author Simeon gbolo This method sets up the math needed to navigate from
	 *         one point to another with a given delta time
	 */
	public void setUpForNavigation(Float new_destination_point)
	{
		startingPoint.setLocation(currentXYlocation);
		currentXYdestination.setLocation(new_destination_point);
		getSlope();
		runningTime = 0;
		state = Node234State.moving;

	}

	/**
	 * @author simeon gbolo
	 * @param path
	 *            the path to set
	 */
	public void setPath(Queue<Float> path)
	{
		this.path = path;
		if (!this.path.isEmpty())
		{
			setUpForNavigation(this.path.poll());
			state = Node234State.moving;
		}
	}

}